Since the advent of the electronic computer in reliable form, workers in the art have given much consideration to systems employing a number of computers functioning together in interrelated fashion to accomplish a given overall task. In some of these multiprocessor systems a large computer utilizes its superior speed and capacity to perform the complex portions of a program, but assigns smaller and slower satellite processors the less complicated and less urgent tasks in order to reduce the load and demands upon the large computer. The large computer is required to undertake the responsibilities of assigning subtasks, making sure that the smaller processors are kept occupied, ascertaining the availability and performance of the smaller processors, and providing a unified result.
Other multiprocessor systems utilize a different approach, employing multiple processors and a common bus system, with the processors having essential equality of function. In this type of system, separate control computers or control systems are often used to monitor the availability and capability of an individual processor for a given subtask, and to control the routing of tasks and information between processors. The proccssors may be arranged and operated so that they themselves monitor the status and availability of the other processors and determine the routing of messages and programs. The common and substantial drawback of these systems is that the software and operating time required for overhead and maintenance functions interfere with the performance of the principal objectives. Problems of routing and monitoring may increase quadratically in relation to the number of processors involved, so that ultimately a disproportionate amount of effort is spent in overhead functions.
The following are some patents that are illustrative of the state of the art:
______________________________________ 3,962,685 Belle Isle 3,962,706 Dennis et al 4,096,566 Borie et al 4,096,567 Millard et al 4,130,865 Heart et al 4,136,386 Annunziata et al 4,145,739 Dunning et al 4,151,592 Suzuki et al ______________________________________
Since the days of the early "Binac" (two parallel processors) and comparable systems it has been recognized that a multiprocessor provides a redundant capability that can substantially improve the overall reliability of an operating system. Actual installations of multiprocessor systems have until recently been quite limited, largely due to the extensive software problems involved. Nonetheless, the advantages of multiprocessor operation for real time applications and other situations in which system down time cannot be tolerated have led to the development of systems which are successful in operation but which nevertheless involve significant commitments to overhead software and operating time. Illustrative of these are U.S. Pat. Nos. 3,445,822, 3,566,363 and 3,593,300, all relating to a system in which multiple computers access a single shared main memory, and in which capabilities and requirements are compared in order to assign tasks optimally to individual processors.
Another example of the prior art is U.S. Pat. No. 4,099,233, in which a number of processors share a single bus and a control unit incorporating a buffer register is used in the transfer of data blocks between a transmitting miniprocessor and a receiving miniprocessor. This concept has been employed in a distributed mail sorting system in Europe.
U.S. Pat. No. 4,228,496 pertains to a commercially successful multiprocessor system in which buses between processors are coupled to bus controllers which monitor transmissions and determine the priority of data transfers between processors, each of which can be coupled in to control a certain part of a number of peripheral devices.
The "Ethernet" system (U.S. Pat. Nos. 4,063,220 and 4,099,024) being jointly promoted by Xerox, Hewlett-Packard and Intel evidences another approach to the problem of intercommunicating between different processors and peripherals. All units are coupled to a common multiple access network and compete for priority. Collision detection is based upon time priority, which in turn means that global capabilities cannot readily be controlled, coordinated or given specificity.
Details of these complex systems can only be fully appreciated by close analysis of the patents and any related publications. However, review will show in each instance that the prioritizing of data transfer and the selection of processors requires extensive intercommunication and supervisory control if tasks are to be shared. Expansion of the systems to include additional processors does not present identical problems with these different systems, but in each instance substantially complicates system software, applications programming, hardware, or all three. Analysis will show that inherent constraints on multiprocessor system size and capability are imposed by the usage of one or two logically passive ohmic busses. While different techniques can be employed to facilitate intercommunication, such as the grouping of subsystems into global resources evidenced in recent U.S. Pat. No. 4,240,143, the amount of useful traffic must reach a limit and variable delays impose insuperable problems when large numbers of processors are used. Situations can arise in which one or more processors become locked out or deadlocked, and these circumstances in turn require added circuitry and software to resolve the problems. The impracticality of substantially extending the number of processors, say to 1024, thus becomes evident.
It is desirable for many applications to depart from the constraints of these existing approaches and to utilize modern technology to best advantage. The lowest cost technology available today is based upon mass produced microprocessors, and high capacity rotating disk memories, such as Winchester technology devices. It is desirable to be able to expand a multiprocessor system without disproportionate or even concomitant software complexity. It is desirable further to be able to handle computer problems that may be characterized as having a distributed structure, in which an overall function can be dynamically subdivided into limited or iterative processing tasks. Virtually all data base machines fall into this category, which also includes such other typical examples as sorting, pattern recognition and correlation, digital filtering, large matrix computations, simulation of physical systems and the like. In all of these situations there is a requirement for widely dispersed, relatively straightforward individual processing tasks with a high instantaneous task load. This situation unduly burdens prior art multiprocessor systems because it tends to increase the time and software involved in overhead, and because practical difficulties arise in implementation of the systems. Using a shared passive bus, for example, propagation rates and data transfer times introduce an absolute barrier as to the rate at which transactions can be processed.
Data base machines thus provide a good example of the need for improved multiprocessor systems. Three basic approaches, namely the hierarchical, network, and relational, have been proposed for the implementation of large scale data base machines. The relational data base machine, which permits easier user access to given data in a complex system by using tables of relationships, has been recognized as having powerful potential. Typical publications, such as an article entitled "Relational Data Base Machines", published by D. C. P. Smith and J. M. Smith, in the March 1979 issue of IEEE Computer magazine, p. 28, U.S. Pat. No. 4,221,003 and articles cited therein illustrate the state of the art.
Sorting machines also provide an example of the need for improved computing architecture. A review of sorting machine theory can be found in Searching and Sorting by D. E. Knuth, pp. 220-246, published (1973) by Addison-Wesley Publishing Co., Reading, Mass. A number of networks and algorithms are disclosed that must be studied in detail to appreciate their limitations, but it is generally true that they are typically complex schemes having only specific sorting purposes. Another example is provided by L. A. Mollaar in an article entitled "A Design for a List Merging Network", in the IEEE Transactions on Computers, Vol. C-28 No. 6, June 1979 at pp. 406-413. The network proposed utilizes external control of network merge elements and requires programming to perform specific functions.
Various workers in the art have considered and are considering specialized memory and system approaches that are intended to improve access to and maintenance of information in a relational data base. These approaches evidence the general recognition of the desirability of the relational data base machine. In their present forms, however, they violate the principle of utilizing the most advantageous cost per bit technology that is presently available, because they inherently require development of futuristic systems of ultimately unknown performance and economic viability. Furthermore, these proposals are so preliminary in nature that they cannot for some time confront the practical difficulties involved with a working data base machine, in which data must not only be accessed, but must further be updated, corrected as necessary, sorted, merged, rolled back, recovered, and otherwise manipulated to meet the user's requirements. The incorporation of other features, such as a capability for expansion of the system, would tend to further delay practical usage of such system.
Significant recent work on relational data base machines has been concerned with responding interactively to ever more complex queries. However, the ability to answer high level and sophisticated queries and the resultant ease of use and user productivity should not impose penalties on the user in terms of throughput and response time. It is also evident that, where a large data base has been accumulated in an organization, the needs of different activities seeking information from the data base can vary widely, and thus to meet all the needs satisfactorily requires extensive knowledge of the system. Although some systems have been devised that perform all of the needed functions, they do so only for small data bases and at great expense.
It is highly desirable for many organizations to be able to utilize a given large main frame system, while obtaining the further cost and reliability advantages of a multiprocessor. If this can be done, all of the organization's existing software and hardware can continue to be used and the effort required to convert to a relational data base system will be minimized and continuity of day-to-day operations will be assured.